A photo shot may sometimes have captured an unnecessary object for the shooter. For example, if the photo has captured unintentionally the face of a stranger who has happened to pass by, an image region representing his or her face needs to be hidden by either filling or pixelization so as to prevent the viewers from identifying him or her when the photo is exposed to general public. As another example, if a person has captured an annoying object which destroys the beauty of the scene he or she has shot, he or she may want to erase that object in some way or other in order to restore the beauty of the photo shot. However, it will take a lot of time and trouble to get such image editing job done manually, and therefore, the quality of the resultant image will heavily depend on the person's skill. For that reason, there is a growing demand for an image interpolating technique for removing such an unwanted object automatically.
According to a conventional image interpolation method, a region of interest on a photo which includes some flaw or superimposed letters to remove is interpolated smoothly by propagating pixel values in surrounding regions over and over again (see Non-Patent Document No. 1, for example). On the other hand, Non-Patent Document No. 2 proposes a “patch matching” technique for making interpolation so that multiple image regions can be merged together continuously and seamlessly by searching for a similar texture region on the basis of a rectangular region called a “patch”. Meanwhile, Patent Document No. 1 teaches estimating the texture in a masked region.